#include <cstdio>
#define min(x,y) (((x)<(y))?(x):(y))

int d[ 1000 ][ 1000 ], f[ 1000 ];

int main( )
{
    int c, n, i, j, ans;
    while ( scanf("%d%d", &c, &n) != EOF )
    {
        for ( i = 0; i < n; i++ )
            for ( j = i; j < n; j++ )
                scanf("%d", &d[ i ][ j ]);
        ans = f[ 0 ] = c + d[ 0 ][ n - 1 ];
        for ( i = 1; i < n; i++ )
        {
            f[ i ] = 0x7fffffff;
            for ( j = 0; j < i; j++ )
                f[ i ] = min( f[ i ], f[ j ] - d[ j ][ n - 1 ] + d[ j ][ i - 1 ] + c + d[ i ][ n - 1 ] );
            ans = min( ans, f[ i ] );
        }
        printf("%d\n", ans);
    }
    return 0;
}